package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 回文链表
 * @author zoum
 * @create 2020/1/10 13:45
 */
public class IsPalindrome {


    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!= null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode reverse = null;
        while (slow!=null){
            ListNode temp = slow.next;
            slow.next = reverse;
            reverse = slow;
            slow = temp;
        }

        while (reverse!= null  && reverse.next != null){
            if (reverse.val != head.val){
                return false;
            }
            reverse = reverse.next;
            head = head.next;
        }

        return true;
    }

    public boolean isPalindrome1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }

        for (int i = 0, j = list.size()-1; i < j; i++, j--) {
            if (!list.get(i).equals(list.get(j))){
                return false;
            }
        }
        return true;
    }
}
